The invention relates generally to the organization of a computer memory. In particular, the invention relates to redundant page identification for a catalogued memory for the purposes of error checking.
Computer systems typically access their memories by the address of the memory. In a simple computer memory, each storage location has a unique address so that when the contents of the memory are accessed, either for reading or for writing, the computer provides an address which is uniquely associated with the desired location. More sophisticated computer memory systems, however, make use of a catalogued memory. By a catalogued memory is meant that a physical memory location in the catalogued memory is at one time assigned to data of one address and at another time to data of a different address. An additional memory, called a directory, is then included in the memory system to provide the correspondence between the physical memory location and the address of the desired data. Thus when a processor desires access to the catalogued memory, it first consults the directory to determine at which physical location in the catalogued memory the addressed data is currently stored. The most common example of a catalogued memory is a cache memory. A cache memory is typically a relatively fast memory that is associated with a much larger but considerably slower mass memory. Large blocks of data, often in the form of pages of 2048 bytes, are transferred from the mass memory to the cache memory. The directory contains the information about where in the cache memory the addressed locations in the mass memory are being stored. Thereafter, the processor, when desiring to access memory, accesses the fast cache memory rather than the slower mass memory. At some point, the contents of the cache memory are transferred to the mass memory and that area of the cache can be used for another page of mass memory once the directory has been updated.
A recent development in computer architecture is to add a cache memory to a disk memory. The disk cache serves a dual purpose. It acts as a buffer between the slow disk and the fast computer bus and it additionally can be randomly accessed by the processor wtihout the need for an independent access to the much slower disk. Such a disk cache is disclosed in U.S. patent application No. 270,951, filed by Dixon et al. on June 5, 1981 and which has issued as U.S. Pat. No. 4,490,782 on Dec. 25, 1984. This application is incorporated herein by reference.
A computer system with a disk cache is illustrated in the block diagram of FIG. 1. A processor has associated therewith a main storage memory 12 of semiconductor memory chips. An I/O channel 14 connects the processor 10 to a plurality of keyboard and display terminals 16 and to an I/O controller 18 that supports four disk units 20, each with a capacity of 200 megabytes. Management of the data storage and data flow between the disk 20 and the processor 10 is provided by a microcomputer 22 using a control program in its read-only storage 24 and further using the random access memory 26.
A handshake logic 28 provides for the interaction between the microprocessor 22 and the processor 10 while a similar handshake logic 30 provides a similar interaction with the disk units 20.
Handshake logic is a means for resolving requests from several sources to use a single data transfer path. One or more of the several sources may, at the same point in time, request permission to use the path. A given central control device in the handshake logic resolves these conflicting requests and grants permission as to which device is allowed to use the data transfer path. The particular priority scheme used in granting access is immaterial to this invention. Once permission has been granted to a particular device, it proceeds to transfer the data. Thus data transfer from a device is always proceeded by a request by the device and a following permission to the device. The handshake logic 28 and 30 may be implemented in a variety of ways well known to those in the art.
The microprocessor 22 controls the logic of the I/O controller 18 through high speed control hardware 32. Data is buffered between the I/O controller 18 and the I/O channel 14 by a data register 34 with another data register 36 providing buffering to the disk units 20. For those applications where caching is not desired, data may be transferred directly between the processor 10 and one of the disk units 20 by way of the data registers 34 and 36, interconnected by a interconnecting bus 38. A semiconductor cache store 40, having a capacity of 384 kilobytes is connected through its own data register 42 to the data registers 34 and 36 by additional interconnecting data buses 44 and 46. Part of the random access memory 26 is devoted to a directory for the pages of the memory space of the disk units 20 currently stored in the cache 40. Of course, other types of cache controllers are possible, such as that disclosed by Porter in U.S. Pat. No. 4,225,922.
In a normal series of operations, the processor accesses a page from one of the disk units 20. That page and usually one or more neighboring pages are transferred from the addressed disk unit 20 into the cache 40. The one requested page is then further transferred from the cache 40 to the processor 10. On subsequent accesses, the directory in the random access memory 26 is consulted to ascertain if the requested page is currently in the cache 40. If so, the access is directly to the cache 40 with no physical access of the disk units 20.
At some point, the cache 40 is filled and further accesses to new pages in the disk units 20 will require that some of the pages in the cache 40 will need to be removed from the cache 40 to the proper disk unit 20. Dixon et al describes an efficient algorithm for determining which of the cached pages should be removed from the cache 40. Of course, when a page is removed from the cache 40 with another page taking its place, the directory in the random access memory 26 needs to be updated.
The 384 kilobyte cache store 40 has a capacity of 393,216 bytes of data and is organized, as illustrated in the table of FIG. 2, into pages of 2 kilobytes (2048 bytes). The 384 kilobyte cache 40 thus can contain 192 pages of data, with the pages arranged on binary boundaries. A total of 19 addressing bits are required to randomly access the cache store 40, as is required because data is transferred through the data registers 13, 34 and 36 a byte at a time. However, because of the binary boundary arrangement, that is, 2048=2.sup.11, the 8 high order addressing bits identify the page while the 11 low order addressing bits refer to the byte within the page. This arrangement has obvious advantages for accessing an entire page, a byte at a time.
It should be emphasized that the page number illustrated in FIG. 2 is the cache page number. The directory contains a table that relates the cache page number to the disk page number, that is, the location in the disk units 20 from which the data in cache originated or to which it will be directed. Dixon et al in the previously cited patent provide an efficient organization for the directory that can be easily updated. It should be obvious that the directory is a crucial component for the described cache memory system since it provides the only means of correctly accessing data that has been cached.
The disk cache, illustrated in FIG. 1, can greatly speed up the flow of data between a disk file and the rest of the computer system. However, the use of cached data introduces a new type of system error. In modern computers, it is generally felt that the error margins on electronic signals are too low to allow the acceptance of an occasional unflagged and uncorrected error. Recorded data can be damaged by noise on data lines as well as media related defects during the writing, storage and reading periods. The problems of data errors have been attached in the past by using parity checking, CRC (cyclic redundancy checking) codes, and ECC (error correcting code). This type of checking and possibly correcting of errors has worked well in the past since the data path has been fairly short. Data buffers have been sequential in nature with little chance of changing the data sequence. However, the introduction of cache memories has resulted in the organization of data dependent upon catalogues or directories. All the data in the cache may have already been checked for parity and, if CRC or ECC is used, errors can be corrected. However, such error detection or correction in the data contributes nothing if the wrong page in the cache has been addressed. The data itself is error free. It is just the wrong data.
General testing of the operability of a cache are described by Joyce et al in U.S. Pat. No. 4,190,885 and by Saltz et al in U.S. Pat. No. 4,357,656. These methods involve a testing algorithm separate from normal accessing.
It is, of course, possible to provide error detection and possibly correction to the memory containing the directory. Shelberg et al. in U.S. Pat. No. 4,084,236 disclose the use of check bits for the addresses contained in the directory so that invalid addresses can be detected. Ready in U.S. Pat. No. 3,840,862 discloses the use of additional tags in the directory which can be used for detecting an invalid cache location. Chang et al. in U.S. Pat. No. 4,197,580 also disclose the use of validity bits in a directory although their validity bits indicate whether the contents of the directory are currently valid. Frananaszek in a technical article entitled "Partitioned Page Transfer from an Electronic Drum" appearing in the IBM Technical Disclosure Bulletin, vol. 25, no. 5, October 1982, at pp. 2621-2622 also discloses a type of validity bit in the directory. Error detection or correction codes applied to the contents of the directory are useful for eliminating errors introduced into the directory. However, electrical line noise may have caused the wrong address to be properly encoded in the directory or a correct address may be transmitted on a noisy line to the cache memory, resulting in a correct address accessing the wrong address in the cache. None of the above patents describe a method useful for detecting this type of error. Finally, the cache algorithm associated with the disk cache is very complex. There are too many possible code paths to allow an exhaustive testing of the code. As a result, there may be unknown code errors that result in an incorrrect correspondence between the directory and the cache.